The field of the present invention is the acquisition, transfer, processing and storage of digital data in graphic arts electronic pre-press applications, and in particular, the compression of such data by means of lossy data compression techniques.
The transfer and storage of data involves ever increasing bandwidth as the uses of electronic information continue to increase. Increased use of "real time" data requires maximum transfer rates with minimum data loss due to processing errors. Accordingly, interest in data compression has increased, both with respect to "lossless" data compression (in which excess data redundancy is eliminated without data loss) and to "lossy" compression, which not only removes redundant data but data judged to be "insignificant" according to criteria specific to the data application.
Although substantial progress has been made in development of lossless compression techniques, notably Shannon-Fano, Huffinan and arithmetic coding, the amount of lossless compression possible in many applications is limited. For image compression, for example, a maximum compression ratio of 2:1 or less is typically realized.
Lossy data compression techniques are capable of substantially greater compression ratios in applications involving time series representations of analog signals (such as speech or music) and two-dimensional arrays representing images (still, motion or video), wherein a portion of the data can be thrown away without noticeable errors of reconstruction. Still further compression can be obtained for varying degrees of tolerance to detectable errors in reconstruction, again depending upon the application. The ability to trade off reconstruction accuracy against compression ratio (i.e., bandwidth) is one of the most attractive aspects of lossy compression for
applications such as network data transfer, real-time data acquisition and processing, and storage of large data sets.
Image processing applications typical of those used in graphic arts electronic pre-press are particularly suitable for lossy data compression techniques, since in many cases the data sets are large (e.g., about 40 Mbytes for an RGB data set representing an 8'.times.10' image scanned at 400 dpi pixel resolution). Such images involve considerable redundancy and can be successfully compressed, using techniques such as the discrete cosine transform (DCT) as embodied in the JPEG standard, to ratios better than 10:1 without perceptual loss, and to 20:1 or better with tolerable losses.
Application of the discrete wavelet transform (also known as hierarchical decomposition) to image compression has also been widely studied, motivated by its ability to decompose an input signal into a series of successively lower resolution reference signals and their associated detail signals. Efficient image coding is then enabled by allocating bandwidth according to the relative importance of information in the lowest subband and detail signals. Such techniques are capable of results comparable to those of the DCT.
The success of such algorithms depends first upon the ability to de-correlate the original data in a reversible (i.e. lossless manner); second upon discarding data deemed "insignificant" according to pre-established criteria using a procedure hereinafter referred to as "quantization";
and, finally upon use of an efficient coding scheme to achieve the maximum bit rate for the data retained, at the same time achieving maximum accuracy of reconstruction. The nature of reconstruction errors (termed "visual artifacts" in the terminology of image processing) becomes a critical factor at the highest usable compression ratios. In the case of DCT-based algorithms, a noticeable "blocking" effect appears as a result of discontinuities between DCT boundaries. For wavelet-based algorithms, a "ringing" effect along edges can often be seen. Accordingly, the efficiency of the quantization and coding steps determines the point at which such artifacts first become objectionable, i.e. the "compressibility" of the image.
It is therefore a general object of the present invention to provide a method and apparatus for data compression.
It is a specific object of the invention to provide a method and apparatus for lossy compression of digital data involving quantization of de-correlated data and encoding at a minimum bit rate, such as to achieve the highest quality reconstruction for a pre-determined compressed data size.
It is another specific object of the invention to provide a method and apparatus for lossy compression of digital data comprising any sequence of numbers, representing time series data, multi-dimensional spatial array data, or a combination thereof.
It is still another specific object of the invention to increase the compressibility of images used in graphic arts electronic pre-press applications by increasing the compression ratios at which visual artifacts first become objectionable.
It is a feature of the invention that the method can be simply implemented.
It is another feature of the invention that coding of the bit stream can be embedded within the processing sequence associated with the method.